package com.test;

import java.util.*;

public class NumCode {
    private List<Integer> temp = new ArrayList<>(9);   //用来洗牌
    private int init_arr[][] = new int[3][3];       //初始状态的八数码
    private int target_arr[][] = new int[3][3];     //目标状态的八数码

    private Node init_node;                          //初始节点S0
    public NumCode() {
        for (int i = 0; i < 9; i++) {
            temp.add(i);
        }
    }
    private void init(){        //给最初的八数码和目标八数码赋值
//        Collections.shuffle(temp);
//        temp = Arrays.asList(5,1,7,8,0,2,4,6,3);
        temp = Arrays.asList(1,2,3,4,5,6,7,8,0);
        int index = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                init_arr[i][j] = temp.get(index);
                index++;
            }
        }
        System.out.println("初始状态的八数码:"+Arrays.deepToString(init_arr));

        //获取初始状态的空格的下标
        int indexOfEmpty = temp.indexOf(0);
        int Empty_i = indexOfEmpty / 3;
        int Empty_j = indexOfEmpty % 3;



//        Collections.shuffle(temp);
//        temp = Arrays.asList(5,1,0,8,4,2,7,6,3);
        temp = Arrays.asList(2,3,4,8,0,5,1,6,7);
        index = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                target_arr[i][j] = temp.get(index);
                index++;
            }
        }
        System.out.println("目标状态的八数码:"+Arrays.deepToString(target_arr));


        //初始化节点S0
        init_node = new Node(0,init_arr,mismatch(init_arr),Empty_i,Empty_j);


    }
    private int mismatch(int arr[][]){      //计算当前节点的八数码中“不在位”的数码个数
        int count = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(target_arr[i][j] != arr[i][j]){
                    count++;
                }
            }
        }
        return count;
    }

    //计算当前节点的八数码交换前和交换后的“不在位”的数码个数之差
    private int differ(int [][] arr,int Empty_i,int Empty_j,int top,int left){
        //当前空格位置(Empty_i,Empty_j),目标位置(Empty_i - left,Empty_j - top)

        //判断移动前，空格位置和目标位置的元素和目标状态的八数码对应元素是否相同
        boolean before_empty = arr[Empty_i][Empty_j] == target_arr[Empty_i][Empty_j];
        boolean before_target = arr[Empty_i - top][Empty_j - left] == target_arr[Empty_i - top][Empty_j - left];

        if(before_empty && before_target){  //如果移动前都在正确位置，那么移动后一定都错位
            return 2;
        }else if(before_empty || before_target){    //如果移动前有且只有一个在正确位置，那么移动后一定都错位
            return 1;
        }else{             //移动前都错位
            //判断移动后，空格位置和目标位置的元素和目标状态的八数码对应元素是否相同
            boolean after_empty = arr[Empty_i - top][Empty_j - left] == target_arr[Empty_i][Empty_j];
            boolean after_target = arr[Empty_i][Empty_j] == target_arr[Empty_i - top][Empty_j - left];

            if(after_empty && after_target){    //移动后都在正确位置
                return -2;
            }else if(after_empty || after_target){  //移动后有一个元素在正确位置
                return -1;
            }else       //移动后两个元素都错位
                return 0;
        }


    }

    //获取移动空格后的八数码
    private int[][] move(int [][] arr,int Empty_i,int Empty_j,int top,int left){
        int[][] result = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                result[i][j] = arr[i][j];
            }
        }

        //交换
        int t;
        t = result[Empty_i][Empty_j];
        result[Empty_i][Empty_j] = result[Empty_i - top][Empty_j-left];
        result[Empty_i - top][Empty_j-left] = t;
        return result;
    }


    public void show(){
        init();     //初始化一下

        //open表
        Queue<Node> open_queue =  new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.value > o2.value)
                    return 1;
                else if(o1.value < o2.value)
                    return -1;
                else
                    return 0;
            }
        });
        open_queue.add(init_node);

        //close表
        Set<IntAry> close_set = new TreeSet<>();

        while(!open_queue.isEmpty()){       //当open表不空时，进行以下操作
            Node cur_node = open_queue.poll();  //获取当前节点,并从open表中删除
            int cur_depth = cur_node.depth;         //当前节点的深度
            int [][]cur_arr = cur_node.arr;     //当前节点的八数码
            int cur_count = cur_node.value - cur_depth;  //当前节点中“不在位的”数码个数
            int cur_i = cur_node.i;
            int cur_j = cur_node.j;

            System.out.println(Arrays.deepToString(cur_arr));
            if(cur_count == 0)      //当前节点中“不在位的”数码个数为0，表明已找到目标八数码
                return;

            //判断当前节点是否可扩展

            if(cur_j >= 1){     //判断能否左移
                int arr[][] = move(cur_arr,cur_i,cur_j,0,1);
                if(!close_set.contains(new IntAry(arr))){
                    int value = cur_count + differ(cur_arr,cur_i,cur_j,0,1) + cur_depth+1;
                    Node node = new Node(cur_depth + 1, arr, value, cur_i, cur_j - 1);
                    open_queue.add(node);
                }


            }
            if( cur_j <= 1){    //判断能否右移
                int arr[][] = move(cur_arr,cur_i,cur_j,0,-1);
                if(!close_set.contains(new IntAry(arr))){
                    int value = cur_count + differ(cur_arr,cur_i,cur_j,0,-1) + cur_depth+1;
                    Node node = new Node(cur_depth + 1, arr, value, cur_i, cur_j + 1);
                    open_queue.add(node);
                }
            }

            if(cur_i >= 1){     //判断能否上移
                int arr[][] = move(cur_arr,cur_i,cur_j,1,0);
                if(!close_set.contains(new IntAry(arr))){
                    int value = cur_count + differ(cur_arr,cur_i,cur_j,1,0) + cur_depth+1;
                    Node node = new Node(cur_depth + 1, arr, value, cur_i - 1, cur_j);
                    open_queue.add(node);
                }
            }
            if(cur_i <= 1){     //判断能否下移
                int arr[][] = move(cur_arr,cur_i,cur_j,-1,0);
                if(!close_set.contains(new IntAry(arr))){
                    int value = cur_count + differ(cur_arr,cur_i,cur_j,-1,0) + cur_depth+1;
                    Node node = new Node(cur_depth + 1, arr, value, cur_i + 1, cur_j);
                    open_queue.add(node);
                }
            }

            close_set.add(new IntAry(cur_arr));     //当前八数码送入close表中

        }


    }
}
//局限性：使用很多数字3，其实应该使用n代替，否则只能适用于八数码